A. Field of Invention
This invention pertains to database systems handling high volumes of data storage edits and/or retrieval. More specifically, a system and methods of creating customized structured data in memory stores (“molding memory”) for storage and retrieval for different needs are described. These methods provide for considerable improvement in both the scalability of requests to be handled and the speed of process time. Examples of areas and industries for which this optimization may be particularly suited include, but are not limited to, telecommunications, financial branch/profit center based systems, biotech, biometrics, chronology based systems (i.e., security systems, electronic card swiping logs, etc.), matrix based systems, credit card agencies, and storage/retrieval based systems. This solution can be used with commodity hardware. Additionally, this solution can be applied to high-end hardware.
B. Description of the Prior Art
The ability to handle a large volume of data along with a rapid response to queries for immediate data retrieval has proven to be mission critical for a growing number of industries and business sectors. As computer processing power increases along with memory storage needs, corporations continue to create programs and databases reliant upon maximizing the resources of ever improving hardware. In order to be effective, from both technological and financial perspectives, these programs and databases continually require faster query/response times with the scalability to handle increasingly large volumes of data queries.
In general, a database is comprised of records and each record is comprised of fields. For example, a database comprising human resource records might have a record for each employee, with each record having a field with data describing start date, home address, salary, etc. In some cases, some fields may be left blank.
Generally, database retrieval systems operate under a query/response approach and the databases are structured to permit expansion as new data become available. Retrieval systems typically involve queries directed to the database. The query is “held” at the database until the proper payload is identified. Then a response message, inclusive of the identified payload, is formulated and sent in response to the originating message.
Currently, one commonly used programming method for increasing the speed and efficiency of responses relates to the way with which data is stored and is referred to as indexing. Indexing, generally, is the process by which the locations of stored records are identified and kept apart from the core table itself. Generally, the indexed data are alphanumeric or numeric. When numeric, the index typically does not always use consecutive numbers, and typically does not use consecutive numbers for later-entered records, but instead uses numbers representative in some computational way of the content of the data. A database index requires a database to have a tabularized structure and itself is a data structure used to improve the speed of retrieval. Using an index, the data in the database are organized in a column or columns for rapid random look-ups and efficient access of ordered records. Each data entry in the database is uniquely identified both to its tabular position and its physical location. Generally, as data are made available for storage in a database, the data are placed in available slots and the locations of the stored data are separately provided to be included in one or more indices. Each unique location identifier is referred to as a key. An index may, in effect, be considered a separate table of keys. Keys may be separately stored so that records may be broken up and stored in a variety of locations of a database, and the keys are necessary to identify all locations and are used to potentially recombine requested data.
In the described methodology, when a query is made to the database, first, the index itself is searched to identify applicable keys. This search may require multiple reads of the index table. In other words, for a single query the index may have to be accessed several times. The identified keys then provide location information for the requested data. An additional lookup is needed to retrieve the payload data. Once the data are retrieved, a response is formulated. Indices may be stored in memory or may be stored separately, and the type and location of storage influences access speed.
Databases in the prior art were historically designed to both assure data integrity (that is, the data in the database are “actual” data and not “artificial” place holders) and for ease of data entry. As a result, databases structured with an index or indices, generally only hold known keys that relate directly to known values. That is, “dummy” data are not included. For example, a database of telephone numbers would not include a non-existing phone number, such as 111-111-1111 and therefore, no key for the non-existent phone number is included in the index. However, a query could be generated for a non-existent record and non-existent key. In general, indices in the prior art are searched using an algorithm and, in general, the algorithm is directed to limiting the search population in successive iterations. When a non-existing key is searched for in the index, the search algorithm will have difficulty identifying the requested key and will generally cause a slowdown causing query response time to lag. In some indexing approaches used today, in order to improve searching in the presence of later-entered records, empty space may initially be left between consecutively numbered keys to permit insertion of additional keys to reduce the frequency of re-indexing. However, when no spaces are left, or when no spaces are made available for internal expansion, then existing keys must be replaced with redirection keys pointing to the end of the index allowing the new keys to be inserted so they are discoverable. Indices may periodically require re-sorting and, consequently, re-indexing, because data in the database has changed.
The speed of retrieval of entries within a database can vary considerably, depending upon the indexing methodology used. To improve retrieval speed, caching may be used in combination with indexing. Caching is implementation and storage of a select group of keys in a unique memory area so as to permit rapid access of the selected keys in the group. Often these are commonly accessed keys or recently accessed keys. When caching is in place, some or all keys may be stored in the cache, which serves to reduce the time for determining the initial key. However, even when caching is used, the index still may need to be searched before the record is accessed.
In addition, either the index and the actual data or both may be cached. Although caching improves retrieval times, caching only improves retrieval times of information that has been cached. Because not all data are cached, the variance in retrieval times may increase in the presence of caching, which could be problematic in some applications.
Access to indices requires multiple reads, and as keys are added to or removed from an index, the sort order deteriorates, requiring an increasing number of reads to access the required key, thus prolonging access time. Although caching may improve some retrieval times, other retrieval times may be lengthy, and as a result, high variability in response times may remain.
In summary, the indexing methodology, even when used with caching, results in wide variability in the time to respond to a database query, and, generally, the mean response time can still be improved. The present invention overcomes this limitation by using a keying system in which a database is pre-assigned to have a finite number of records with a key assigned for every possible entry within the required key range, thus eliminating the need for future intermediate insertion of additional keys.
Commercial databases, by design, are all-purpose without specificity to any single business or its requirements. Currently, commercial database applications generally rely on memory caching. The present invention discloses memory molding as an alternative to indexing. In the present invention the physical memory is structured to the specific needs of the given application. By molding memory, the performance speed of responses to queries dramatically increases over commercial database applications now in use.